package com.fw.leetcode.search;

import com.fw.leetcode.LeetCode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 104. Maximum Depth of Binary Tree
 *
 * Given the root of a binary tree, return its maximum depth.
 * A binary tree's maximum depth is the number of nodes along the longest
 * path from the root node down to the farthest leaf node.
 *
 * Example 1:
 *                 3
 *         9              20
 *    null  null       15    7
 *
 *  Input: root = [3,9,20,null,null,15,7]
 *  Output: 3
 *
 * Example 2:
 *  Input: root = [1,null,2]
 *  Output: 2
 *
 * Constraints:
 *  The number of nodes in the tree is in the range [0, 104].
 *  -100 <= Node.val <= 100
 */
public class Num_0104 implements LeetCode {
    private interface Solution extends Tree {
        int maxDepth(TreeNode root);

        default void assertExpected(Integer[] root, int expected) {
            TreeNode rooNode = buildBinaryTree(root);
            if (maxDepth(rooNode) != expected) {
                maxDepth(rooNode);
            }
        }
    }

    private static class MyDfsSolution implements Solution {

        @Override
        public int maxDepth(TreeNode root) { // 最优：深度优先搜索(递归)：时O(n) 空O(log n)
            /*
             *  0                0
             *  1         1            2
             *  2      3     4      5     6
             */
            if (root == null) return 0;
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }

    private static class MyBfsSolution implements Solution {

        @Override
        public int maxDepth(TreeNode root) { // 其次：广度优先搜索(队列)：时O(n) 空O(<n)依队列长度，最坏情况O(n)
            /*
             *  0                0
             *  1         1            2
             *  2      3     4      5     6
             */
            if (root == null) {
                return 0;
            }
            int depth = 0;
            Queue<TreeNode> queue = new ArrayDeque<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                depth++; // 当前层非空，深度加 1
                int layerSize = queue.size();
                while (layerSize-- > 0) { // 遍历当前层节点数，入队下层子节点
                    TreeNode node = queue.poll();
                    if (node == null) {
                        continue;
                    }
                    if (node.left != null) {
                        queue.add(node.left);
                    }
                    if (node.right != null) {
                        queue.add(node.right);
                    }
                }
            }
            return depth;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyBfsSolution();
        solution.assertExpected(new Integer[]{3,9,20,null,null,15,7}, 3);
        solution.assertExpected(new Integer[]{1,null,2}, 2);
    }
}
